package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code12MinimumWindowSubstring {

    public String minWindow(String s, String t) {
        int sl = s.length();
        int tl = t.length();
        if (sl < tl) {
            return "";
        }

        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        // 记录 t 字符串中各字符出现次数
        int[] need = new int[128];
        for (char c : str2) {
            need[c]++;
        }

        // 记录最小子串的最左位置
        int minL = 0;
        // 记录最小子串长度
        int min = Integer.MAX_VALUE;
        // 标记是否完整包含 t
        int full = tl;
        for (int l = 0, r = 0; r < sl; r++) {
            // 当前位置包含所需字符
            if (need[str1[r]] > 0) {
                full--;
            }
            // 当前字符从右入窗口
            need[str1[r]]--;

            // 完全包含 t
            if (full == 0) {
                // 左边窗口尝试移除不在 t 中的字符, 以达到最小窗口
                while (l < r && need[str1[l]] < 0) {
                    need[str1[l]]++;
                    l++;
                }
                // 更新下最小结果
                if (r - l + 1 < min) {
                    minL = l;
                    min = r - l + 1;
                }
                // 左边窗口尝试减小
                need[str1[l]]++;
                l++;
                full++;
            }
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(minL, minL + min);
    }
}
